# 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
# 
#  
# 
#  
#  
#  示例 1： 
#  
#  
# 
#  
# 输入：s = "(()"
# 输出：2
# 解释：最长有效括号子串是 "()"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = ")()())"
# 输出：4
# 解释：最长有效括号子串是 "()()"
#  
# 
#  示例 3： 
# 
#  
# 输入：s = ""
# 输出：0
#  
# 
#  
# 
#  提示： 
# 
#  
#  0 <= s.length <= 3 * 10⁴ 
#  s[i] 为 '(' 或 ')' 
#  
# 
#  Related Topics 栈 字符串 动态规划 👍 2628 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """
        思路一：在每次成功匹配括号时，计算下这个括号的长度（索引之差+1即为长度）
        :param s:
        :return:
        """
        # stack = [-1]
        # maxL = 0
        # for index, c in enumerate(s):
        #     if c == "(":
        #         stack.append(index)
        #     else:
        #         stack.pop()
        #         if not stack:
        #             stack.append(index)
        #         else:
        #             maxL = max(maxL, index - stack[-1])
        #
        # return maxL
        """
        思路二：动态规划
        """
        # dp[i]表表示以第i个元素为结尾的连续括号数量为dp[i]
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        if s[0:2] == "()":
            dp[1] = 2
        # dp[0]恒为0，1已经算出，故从2开始
        for i in range(2, n):
            if s[i] == "(":
                dp[i] = 0
            else:
                if s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
                # 若前一个字符不为左括号，为右括号
                else:
                    if i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                        dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                    # 若 s[i-dp[i-1]-1] == ")" 则当前这个）够不成闭合的括号，所以dp[i] = 0,无需操作
        return max(dp)


print(Solution().longestValidParentheses(s="(()))())("))
